package topic;

import java.util.Arrays;

/*
    快速排序算法
 */
public class QuickSort {
    public static void main(String[] args) {
        int arr[]={16,15,1,30,45,23,9};
        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
    }

    //对一个数组进行快速排序
    public static void quickSort(int arr[],int start,int end){
        //当数组最少有两个元素时
        if(start<end){
            //对数组进行划分,得到基准位置的下标
            int i=partition(arr,start,end);
            //对小于基准的部分再进行排序
            quickSort(arr,start,i-1);
            //对大于基准的部分进行排序
            quickSort(arr,i+1,end);
        }
    }

    //划分算法
    public static int partition(int arr[],int start,int end){
        int i=start;
        int j=end;
        //选择第一个元素作为基准
        int temp=arr[i];
        while (i!=j){
            //从右向左扫描第一个小于temp的数
            while (j>i && arr[j]>=temp){
                j--;
            }
            arr[i]=arr[j];
            //从左向右扫描第一个大于temp的数
            while (i<j && arr[i]<=temp){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=temp;
        System.out.println(Arrays.toString(arr));
        return i;
    }

}
